package priv.pront.code.national.acwing.dp.interval;

import java.util.Scanner;

/**
 * @Description:
 * @Author: pront
 * @Time:2023-05-23 19:43
 */
public class Acwing479_加分二叉树 {

    static int[][] root;
    static int n;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        int[] a = new int[n + 1];
        int[][] dp = new int[n + 1][n + 1];
        root = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            a[i] = scanner.nextInt();
            dp[i][i] = a[i];
            root[i][i] = i;
        }
        for (int len = 2; len <= n; len++) {
            for (int i = 1; i + len - 1 <= n; i++) {
                int j = i + len - 1;
                for (int k = i; k <= j; k++) {
                    int left = k == i ? 1 : dp[i][k - 1];
                    int right = k == j ? 1 : dp[k + 1][j];
                    int ans = left * right + a[k];
                    if (ans > dp[i][j]) {
                        dp[i][j] = ans;
                        root[i][j] = k;
                    }
                }
            }
        }
        System.out.println(dp[1][n]);
        dfs(1, n);
    }

    private static void dfs(int l, int r) {
        if (l > r || r > n) return;
        int k = root[l][r];
        System.out.print(k + " ");
        dfs(l, k - 1);
        dfs(k + 1, r);
    }
}
